package com.zx._12_算法.数据结构.link;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Demo6
 *         给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表
 *         k 是一个正整数，它的值小于或等于链表的长度。
 *         如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序
 *         给定这个链表：1->2->3->4->5
 *         当 k = 2 时，应当返回: 2->1->4->3->5
 *         当 k = 3 时，应当返回: 3->2->1->4->5
 *
 *         你的算法只能使用常数的额外空间。
 *         你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * @author: zhangxue
 * @date: 2019年7月27日下午8:34:11
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class Demo6 {

    /**
     * 复杂度分析:
     * 时间复杂度：O(n * K)
     * 空间复杂度：O(1)。除了几个必须的节点指针外，并没有占用其它空间。
     *
     * @param args
     * @date: 2019年8月15日下午10:50:44
     * @author: zhangxue
     */
    public static void main(String[] args) {
        Node<Integer> nodes1 = getNodes(1, 2, 3, 4, 5);

        print(nodes1);

        Node<Integer> newHead = reverseKGroup(nodes1, 2);

        print(newHead);
    }

    public static Node<Integer> reverseKGroup(Node<Integer> head, int k) {
        Node<Integer> newHead = null;//新的链表的头

        Node<Integer> begin = null;//本次迭代开始的上一个
        Node<Integer> end = head; //本次迭代结束的下一个
        Node<Integer> pointer = head;//用来下面的指针

        while (true) {
            Node<Integer> first = end;//本次迭代的第一个节点

            // 判断节点是否走
            boolean isReverse = true;
            for (int i = 0; i < k - 1; i++) {
                if (pointer == null || pointer.next == null) {
                    isReverse = false;
                    break;
                }
                pointer = pointer.next;
            }

            if (isReverse) {
                //1. 重新定义头尾的对接处
                end = pointer.next;// 获得本地迭代的尾部的对接处
                pointer.next = null;// 将本地迭代的最后一个节点的next置为null

                // 只对这个长度为K的链表进行翻转
                Node<Integer> node = reverse(first);
                // 这个时候，first 已经变成本地迭代最后一个了，

                // 2.将K长度的链表的开头接入在总的链表里面
                if (begin != null) {
                    begin.next = node;// 对接开头
                }
                first.next = end;// 对接结尾

                // 3. 初始化下个迭代的begin和end
                pointer = first.next;// pointer中的链表在调用reverse的时候，指针已经发生了变化
                begin = first;
                end = pointer;

                // 初始化返回的新的链表
                if (newHead == null) {
                    newHead = node;
                }
            } else {
                if (newHead == null) {
                    newHead = head;
                }
                break;
            }
        }
        return newHead;
    }

    public static Node<Integer> reverse(Node<Integer> head) {
        Node<Integer> curNode = head;
        Node<Integer> curNextNode = curNode.next;
        curNode.next = null;

        while (curNextNode != null) {
            Node<Integer> next = curNextNode;
            Node<Integer> nextNext = next.next;

            curNextNode.next = curNode;

            curNode = next;
            curNextNode = nextNext;
        }

        return curNode;
    }

    public static void print(Node<Integer> head) {
        Node<Integer> node = head;
        String s = "";
        while (node != null) {
            s += node.data + ", ";
            node = node.next;
        }
        System.out.println("link = [" + s.substring(0, s.length() - 2) + "]");
    }

    public static Node<Integer> getNodes(Integer... nums) {
        Node<Integer> result = new Node<>();
        result.data = nums[0];

        Node<Integer> node = result;
        for (int i = 1; i < nums.length; i++) {
            Node<Integer> node2 = new Node<>();
            node2.data = nums[i];
            node.next = node2;
            node = node2;
        }
        return result;
    }


    static class Node<T> {

        T data;
        Node<T> next;

        @Override
        public String toString() {
            return "Node [data=" + data + ", next=" + next + "]";
        }
    }
}
